"""
https://leetcode.cn/problems/decode-string/description/

394. 字符串解码
已解答
中等
相关标签
相关企业
给定一个经过编码的字符串，返回它解码后的字符串。

编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。

此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

 

示例 1：

输入：s = "3[a]2[bc]"
输出："aaabcbc"
示例 2：

输入：s = "3[a2[c]]"
输出："accaccacc"
示例 3：

输入：s = "2[abc]3[cd]ef"
输出："abcabccdcdcdef"
示例 4：

输入：s = "abc3[cd]xyz"
输出："abccdcdcdxyz"
 

提示：

1 <= s.length <= 30
s 由小写英文字母、数字和方括号 '[]' 组成
s 保证是一个 有效 的输入。
s 中所有整数的取值范围为 [1, 300] 

"""
from typing import List


class Solution:
    """
    本题难点在于审核嵌套识别[]
    包括嵌套[]存储在哪儿
    比较符合栈的取数规则，即：数字和要使用的[]总是相邻的，且有存数的必要

    官方思路和本人思路比较相似。
    区别在于有几个优化点：
    判定是否是数字，可使用ch.isdigit()

    """

    def decodeString(self, s: str) -> str:
        i=0
        str_stack:List[List[str]]=[[]]
        num_stack:List[int]=[1]
        while i<len(s):
            # 初始倍数
            num=0
            
            # 先收集数字（可能没有）
            while ord('0')<=ord(s[i])<=ord('9'):
                num=num*10+(ord(s[i])-ord('0'))
                i+=1

            # 如果num>0，则表示必定为[]的模式，否则必定为直接拼接模式
            if num==0:
                # 单纯为英文，至少有一个(此处相当于扩充当前英文栈的基础内容)
                en_idx=i
                while i<len(s) and ord('a')<=ord(s[i])<=ord('z'):
                    i+=1
                if i>en_idx:
                    str_stack[-1].append(s[en_idx:i])
                    continue
            
            # 此处必定为[ab...]的模式
            if s[i]=='[':
                str_stack.append([])
                num_stack.append(num)
                i+=1
                continue

            # 对栈pop
            if s[i]==']':
                str_list=str_stack.pop()
                num=num_stack.pop()
                str_stack[-1].append(''.join(str_list)*num)
                i+=1
                continue
        
        return ''.join(str_stack[0])
                

if __name__=='__main__':
    sol=Solution()
    s='abc3[cd]xyz'
    res=sol.decodeString(s)
    print(res)
    pass